package algorithm;

import java.util.ArrayList;
import java.util.List;

//递归
public class AlgoC {
	/**
	 * 第一要素，明确函数干什么 递归函数的核心是解决一个规模更小的同类型问题。 设计递归函数时，首先要确定函数的功能，给定输入，函数返回什么结果
	 * 示例：计算n的阶乘（假设n不为0）f(n) 返回 n 的阶乘 第二要素：寻找递归结束条件 递归函数必须有终止条件，否则会无限递归，导致栈溢出。
	 * 终止条件通常是问题的最小规模，能够直接给出答案的情况。 示例： 计算n的阶乘，当n <= 2时，直接返回n 第三要素：找出函数的等价关系式（递归关系）
	 * 递归函数通过将原问题分解成规模更小的同类型问题，调用自身解决。 递归关系是递归函数的核心，描述如何从规模较小的问题推导规模较大的问题。 示例：
	 * 计算n的阶乘，f(n) = n * f(n-1)
	 */
	public static void main(String[] args) {
		permutation(2, 1, new ArrayList<Integer>());
	}

	/*
	 * 计算n的阶乘，f(n) = n * f(n-1) = 1 * 2 ... * n
	 */
	static int multiply(int n) {

		if (n == 1) {
			return 1;
		}
		return n * multiply(n - 1);
	}

	/**
	 * 最大公约数 辗转相除法
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	static int gcd(int a, int b) {
		if (b == 0) {
			return a;
		}
		return gcd(b, (a % b));
	}

	/**
	 * 最大公约数2 辗转相除法
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	static int gcd_classic(int a, int b) {
		while (b != 0) {
			int temp = b;
			b = a % b;
			a = temp;
		}
		return a;
	}

	/**
	 * 最小公倍数
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	static int lcm(int a, int b) {
		return a * b / gcd_classic(a, b);
	}

	/**
	 * FJ字符串 n = 1, s = A; n = 2, s = ABA; n = 3, s = ABACABA; n = 4, s =
	 * ABACABADABACABA
	 * 
	 * @param n
	 * @return s
	 */
	static String fjs(int n) {
		if (n == 1)
			return "A";
		else
			return fjs(n - 1) + (char) ('A' + n - 1) + fjs(n - 1);
	}

	/**
	 * 从1~n中输出所有可能的排列方案
	 * 
	 * 思路：dfs深度优先遍历+回溯
	 * 
	 * @param n    总共的数
	 * @param idx  当前处理哪一位
	 * @param list 存储排列方案
	 */
	static void permutation(int n, int idx, List<Integer> list) {
		if (idx > n) {
			System.out.println(list.toString());
			return;
		}
		// 不选当前数
		permutation(n, idx + 1, list);
		// 选当前数
		list.add(idx);
		permutation(n, idx + 1, list);
		// 回溯，删除最后一个元素
		list.remove(list.size() - 1);
	}
}
